package com.algorithm.cjm.jiaocai.ch5;

import java.util.Arrays;

/**
 * Created by jieming.chen on 2020/2/3
 */
public class Example24 {

    static void countingTower() {
        int[][] data = new int[][]{{9}, {12, 15}, {10, 6, 8}, {2, 18, 9, 5}, {19, 7, 10, 4, 16}};
        int[][] d = new int[50][50];

        // 早期阶段动态规划决策的结果是一组数据，且这次的决策结果是下次决策的唯一依据(无后效性)，所以必须存储每一次的决策结果
        for (int i = data.length - 1; i >= 0; i--) {
            for (int j = 0; j < data[i].length; j++) {
                d[i][j] = Math.max(d[i + 1][j], d[i + 1][j + 1]) + data[i][j];
            }
        }
        System.out.println(Arrays.deepToString(d));
    }

    public static void main(String[] args) {
        countingTower();
    }
}
